#include "DoubleLinkList.h"
#include <iostream>

DoubleLinkList::DoubleLinkList():size(0)
{
    head = tail = new Node(0);
    Free = nullptr;
    Compare = nullptr;
    Print = nullptr;
}

DoubleLinkList::DoubleLinkList(const DoubleLinkList &list)
{
    size = list.size;
    head = tail = new Node(0);
    Node *tp = head;
    Node *travelPoint = list.head->next;
    while(travelPoint != nullptr)
    {
        Node *newNode = new Node(travelPoint->value);
        tp->next = newNode;
        newNode->prev = tp;
        newNode->next = nullptr;
        tp = tp->next;
        travelPoint = travelPoint->next;
    }
    tail = tp;
}

DoubleLinkList &DoubleLinkList::operator=(const DoubleLinkList &list)
{
    while(head != nullptr)   //销毁当前链表
    {
        Node *nextNode = head->next;  //下一个节点存下来
        delete head;
        head = nextNode;
    }
    tail = nullptr;  //此时首尾指针都为空

    size = list.size;
    head = tail = new Node(0);  //初始化头节点和尾节点都指向这个值为0的新节点
    Node *tp = head;
    Node *travelPoint = list.head->next;
    while(travelPoint != nullptr)
    {
        Node *newNode = new Node(travelPoint->value);
        tp->next = newNode;
        newNode->prev = tp;
        newNode->next = nullptr;
        tp = tp->next;
        travelPoint = travelPoint->next;
    }
    tail = tp;
    return *this;
}

DoubleLinkList::~DoubleLinkList()
{
    while(head != nullptr)
    {
        Node *nextNode = head->next;  //下一个节点存下来
        delete head;
        head = nextNode;
    }
    tail = nullptr;
}

void DoubleLinkList::SetFreeFunc(void (*Free)(ElementType))
{
    this->Free = Free;
}

void DoubleLinkList::SetCompareFunc(int (*Compare)(ElementType, ElementType))
{
    this->Compare = Compare;
}

void DoubleLinkList::SetPrintFunc(void (*Print)(ElementType))
{
    this->Print = Print;
}

void DoubleLinkList::InsertTail(const ElementType &element)
{
    Node *newNode = new Node(element);
    if(tail == nullptr)
    {
        head = tail = newNode;
    }
    else
    {
        tail->next = newNode;
        newNode->prev = tail;
        tail = newNode;
    }
    size++;
}

void DoubleLinkList::InsertByIndex(size_t index, const ElementType &element) 
{
    if(index >= size)
    {
        std::cout<<"位置非法!\n";
        return;
    }
    Node *travelPoint = head;
    for(size_t i = 0; i < index; i++)
    {
        travelPoint = travelPoint->next;
    }
    Node *newNode = new Node(element);
    newNode->next = travelPoint->next;
    newNode->prev = travelPoint;

    travelPoint->next = newNode;
    newNode->next->prev = newNode;
    size++;
}

void DoubleLinkList::RemoveByIndex(size_t index)
{
    if(index >= size)
    {
        std::cout<<"位置非法!\n";
        return;
    }
    Node *travelPoint = head->next;
    for(size_t i = 0; i < index; i++)
    {
        travelPoint = travelPoint->next;
    }
    if(index != size - 1)
    {
        Node *freeNode = travelPoint;
        freeNode->prev->next = freeNode->next;
        if(freeNode->next)
            freeNode->next->prev = freeNode->prev;
        else
            tail=freeNode->prev;
        delete freeNode;
        size--;
    }
}

void DoubleLinkList::RemoveByElement(const ElementType &element)
{
    Node *travelPoint = head->next;
    while(travelPoint != nullptr)
    {
        if(!Compare(travelPoint->value, element))
        {
            Node *freeNode = travelPoint;
            travelPoint = freeNode->next;
            freeNode->prev->next = freeNode->next;
            if(freeNode->next)
                freeNode->next->prev = freeNode->prev;
            else
                tail = freeNode->prev;
            delete freeNode;
            size--;
        }
        else
            travelPoint = travelPoint->next;
    }
}

DoubleLinkList::ElementType *DoubleLinkList::FindByIndex(size_t index)
{
    if(index >= size)
        return nullptr;
    Node *travelPoint = head->next;
    for(size_t i = 0; i < index; i++)
    {
        travelPoint = travelPoint->next;
    }
    return &travelPoint->value;
}

DARRAY::DynamicArray DoubleLinkList::FindByElement(const ElementType &element)
{
    DARRAY::DynamicArray array;
    Node *travelPoint = head->next;
    while(travelPoint != nullptr)
    {
        if(!Compare(travelPoint->value, element))
            array.InsertTail(travelPoint->value);
        travelPoint = travelPoint->next;
    }
    return array;
}

void DoubleLinkList::UpdateByIndex(size_t index, const ElementType &element)
{
    if(index >= size)
    {
        std::cout<<"位置非法!\n";
        return;
    }
    Node *travelPoint = head->next;
    for(size_t i = 0; i < index; i++)
    {
        travelPoint = travelPoint->next;
    }
    travelPoint->value = element;
}

void DoubleLinkList::UpdateByElement(const ElementType &oldValue, const ElementType &newValue)
{
    Node *travelPoint = head->next;
    while(travelPoint != nullptr)
    {
        if(!Compare(travelPoint->value, oldValue))
        {
            travelPoint->value = newValue;
        }
        travelPoint = travelPoint->next;
    }
}

void DoubleLinkList::Sort()
{
    FastSort(head->next, nullptr);
}

void DoubleLinkList::show()
{
    std::cout<<"size : "<<size<<std::endl;  //打印链表的大小
    Node *travelPoint = head->next;  //从第一个节点开始
    while(travelPoint != nullptr)  //链表还没有结束
    {
        std::cout<<travelPoint->value<<" ";  //打印节点的值
        travelPoint = travelPoint->next;  //遍历指针往后走
    }
    std::cout<<std::endl;

    travelPoint = tail;
    while(travelPoint != head)
    {
        std::cout<<travelPoint->value<<" ";
        travelPoint = travelPoint->prev;
    }
    std::cout<<std::endl;
}

void DoubleLinkList::FastSort(Node *start, Node *end)
{
    if(start == end)
    {
        return ;
    }
    Node *temp = start;  //基准值指针
    Node *slow = start;  //慢指针
    Node *fast = start->next;  //快指针
    while(fast != end)  //快指针没有到结尾
    {
        //  快指针指向的值比基准值小
        if(fast->value < temp->value)
        {
            slow = slow->next;
            std::swap(slow->value,fast->value);  //交换快慢指针的值
        }
        fast = fast->next;
    }
    std::swap(temp->value, slow->value);  //将基准值归位
    FastSort(start,slow);  //[start,slow)
    FastSort(slow->next,end);
}
